package com.example.algorithms.sum;

import com.example.algorithms.sort.QuickSort;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author Zhang Jie
 * @Date 10/16/20
 * @Version 1.0
 */

public class ThreeNumSum {

    /**
     * 通过hash查找，类似于TwoNumSum
     * 假定arr中不包含重复值
     * @param sum
     * @param arr
     * O(n^2)
     */
    public static void findByHash(int sum, int[] arr){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<arr.length;i++){
            int surplus = sum-arr[i];
            for(int j=i+1;j<arr.length;j++){
                int surplus2=surplus-arr[j];
                if(map.containsKey(surplus2)){
                    System.out.printf("{%d,%d,%d}",i,j,map.get(surplus2));
                }
                map.put(arr[j],j);
            }
            map.clear();
        }
    }

    /**
     * 利用双指针
     * O(n^2)
     */
    public static void findByDouPoints(int sum, int[] arr){
        //1. 排序
        QuickSort.sortUp(arr);
        //2. 查找
        for(int i=0;i<arr.length;i++){
            int surplus = sum-arr[i];
            int j=i+1,k=arr.length-1;
            while(j<k){
                int sum0=arr[j]+arr[k];
                if(sum0<surplus){
                    j++;
                }else if(sum0>surplus){
                    k--;
                }else{
                    //因为已经排序了，所以输出数值
                    System.out.printf("{%d,%d,%d}",arr[i],arr[j],arr[k]);
                    j++;
                    k--;
                }
            }
        }
    }
}
